//剑指offer30题.
//连续子数组的最大和
//思路：动态规划
1、定义一个状态，这是一个最优解的结构特征
//f(i)以array[i]结尾的连续子序列的最大和
2、进行状态递推，得到递推公式
//f(1)=max(array[0]+array[1],array[1])	--->max(f(1-1)+array[1],array[1])
//......
//f(i)=max(f(i-1)+array[i],array[i])
3、进行初始化
//f(0)=array[0];
4、返回结果
//max(f(i),result)

public class Solution{
	public int FindGreatestSumOfSubArray(int[] array){
	if(array.length==0)return 0;
	int[] tmp=new int[array.length];
	tmp[0]=array[0];
	for(int i=1;i<array.length;i++){
		tmp[i]=Math.max(tmp[i]+array[i],array[i]);
		}
	int result=tmp[0];
	for(int i=1;i<array.length;i++){
		result=Math.max(tmp[i],result);
		}
	return result;
	}
}